UVa/515 - King/515.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <numeric>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXN = 105;
  28
  29 vector<pair<int, int> > g[MAXN];
  30 int d[MAXN];
  31
  32 int main(){
  33   int n, m;
  34   while (cin >> n >> m && n){
  35     n++;
  36     for (int i=0; i<n; ++i) g[i].clear();
  37     while (m--){
  38       int si, ni, a, b, c; string op;
  39       cin >> si >> ni >> op >> c;
  40       a = si + ni;
  41       b = si - 1;
  42       if (op == "lt"){
  43         g[b].push_back(make_pair(a, c-1));
  44       }else{
  45         g[a].push_back(make_pair(b, -c-1));
  46       }
  47     }
  48
  49     int dummy = n+1;
  50     for (int i=0; i<n; ++i) g[dummy].push_back(make_pair(i, 0));
  51
  52     fill(d, d+n, INT_MAX / 3);
  53     d[dummy] = 0;
  54     for (int repeat = true, cota = n; repeat && --cota; ){
  55       repeat = false;
  56       for (int u=0; u<n; ++u){
  57         for (int k=0; k<g[u].size(); ++k){
  58           int v = g[u][k].first, w = g[u][k].second;
  59           if (d[u] + w < d[v]){
  60             d[v] = d[u] + w;
  61             repeat = true;
  62           }
  63         }
  64       }
  65     }
  66
  67     bool solvable = true;
  68     for (int u=0; u<n; ++u){
  69       for (int k=0; k<g[u].size(); ++k){
  70         int v = g[u][k].first, w = g[u][k].second;
  71         if (d[u] + w < d[v]){
  72           solvable = false;
  73           u = n; break; //ultrabreak
  74         }
  75       }
  76     }
  77
  78     if (solvable) puts("lamentable kingdom");
  79     else puts("successful conspiracy");
  80   }
  81
  82 return 0;
  83 }